<?php
/**
 * 快速排序: 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的值均比另一部分记录的值小
 * 再分别对这两部分记录进行下一趟排序，以达到整个序列有序。
 * PHP 内部针对数组使用的方法就是快排
 * User: yuesir
 * @author //github.com/yuesir
 */


/**
 * 快速排序
 * @param array $bucket
 * @return array
 */
function quickSort(array &$bucket) {
    if ( empty($bucket) || 1 == count($bucket)) return $bucket;

    $ruler = $bucket[0];
    $count = count($bucket);
    for ($i = 1; $i < $count; $i++) {
        if ($bucket[$i] >= $ruler) {
            $bigger[] = $bucket[$i];
        } else {
            $smaller[] = $bucket[$i];
        }
    }

    $left   = quickSort($smaller);
    $right  = quickSort($bigger);

    return array_merge($left, array($ruler), $right);

}